package logic;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Random;

/**
 * @author Marco Gallardo Casu
 * 
 */
public class TreeBin {

	private int depth;
	private int minDepth;
	private int maxDepth;
	private int numNodes;
	private Operand operand;
	private Operation operator;
	private TreeBin son;
	private TreeBin brother;
	private TreeBin father;

	public TreeBin(int minDepth, int maxDepth, Operand operand,
			Operation operator) {
		this.minDepth = minDepth;
		this.maxDepth = maxDepth;
		this.operand = operand;
		this.operator = operator;
	}

	public TreeBin(int minDepth, int maxDepth, Operand operand,
			Operation operation, int depth, int numNodes, TreeBin father) {
		this.minDepth = minDepth;
		this.maxDepth = maxDepth;
		this.operand = operand;
		this.operator = operation;
		this.depth = depth;
		this.numNodes = numNodes;
		this.father = father;
	}

	public TreeBin(int minDepth, int maxDepth, TreeBin father) {
		this.father = father;
		this.minDepth = minDepth;
		this.maxDepth = maxDepth;
		if (minDepth >= 0 && minDepth <= maxDepth) {
			if (minDepth > 0) {
				genSubTree(minDepth, maxDepth);
			} else {
				genSubTree2(minDepth, maxDepth);
			}
		} else {
			genSubTree2(minDepth, maxDepth);
		}
	}

	public TreeBin clone() {
		TreeBin t = clone(father);
		t.setFather(father);
		return t;
	}

	public boolean contains(Object object) throws ClassCastException,
			NullPointerException {
		if (object == null) {
			throw new NullPointerException(
					"Null pointer in the object received.");
		}

		if (!(object instanceof TreeBin)) {
			throw new ClassCastException("The object received isn't a Tree.");
		}

		TreeBin t1 = this;
		TreeBin t2 = (TreeBin) object;

		boolean finish = false;
		while (!finish && t1 != null && t2 != null) {
			Operand operand1 = t1.getOperand();
			Operand operand2 = t2.getOperand();
			Operation operation1 = t1.getOperation();
			Operation operation2 = t2.getOperation();
			t1 = t1.getSon();
			t2 = t2.getSon();
			// While nodes in the general tree and the objects are equals, down
			// a level
			while (operation1 == operation2 && operand1 == operand2
					&& t1 != null && t2 != null) {
				operand1 = t1.getOperand();
				operand2 = t2.getOperand();
				operation1 = t1.getOperation();
				operation2 = t2.getOperation();
				t1 = t1.getSon();
				t2 = t2.getSon();
			}

			if (t1 != null && t2 != null) {
				t1 = t1.getBrother();
				// When the nodes aren't equals, look if they are brothers.
				while ((operation1 != operation2 && operand1 == operand2 || operation1 == operation2
						&& operand1 != operand2)
						&& t1 != null) {
					if (t1.isLastSon() && operand1 != operand2) {
						finish = true;
					}
					operand1 = t1.getOperand();
					operation1 = t1.getOperation();
					t1 = t1.getBrother();
				}

			}

		}

		return t2 == null ? true : false;
	}

	@Override
	public boolean equals(Object object) {
		if (object == null) {
			return false;
		}
		if (!(object instanceof TreeBin)) {
			return false;
		}

		TreeBin t = (TreeBin) object;

		if (isLeaf() && isLastSon()) {
			return operand == t.getOperand();
		} else if (isLastSon()) {
			return operator == t.getOperation() && son.equals(t.getSon());
		} else if (isLeaf()) {
			return operand == t.getOperand() && brother.equals(t.getBrother());
		} else {
			return operator == t.getOperation() && son.equals(t.getSon())
					&& brother.equals(t.getBrother());
		}
	}

	/**
	 * Evaluate the result of the tree
	 * 
	 * @param a
	 *            Control.
	 * @param d
	 *            Data.
	 * @return the result.
	 */
	public boolean evaluate(boolean[] a, boolean[] d) {
		boolean sol = false;
		if (operand == null) {
			ArrayList<TreeBin> son = getSons();
			switch (operator) {
			case IF:
				sol = son.get(0).evaluate(a, d) ? son.get(1).evaluate(a, d)
						: son.get(2).evaluate(a, d);
				break;
			case AND:
				sol = son.get(0).evaluate(a, d) && son.get(1).evaluate(a, d);
				break;
			case OR:
				sol = son.get(0).evaluate(a, d) || son.get(1).evaluate(a, d);
				break;
			default:
				sol = !son.get(0).evaluate(a, d);
				break;
			}
		} else {
			switch (operand) {
			case A0:
				sol = a[0];
				break;
			case A1:
				sol = a[1];
				break;
			case D0:
				sol = d[0];
				break;
			case D1:
				sol = d[1];
				break;
			case D2:
				sol = d[2];
				break;
			default:
				sol = d[3];
				break;
			}
		}
		return sol;
	}

	/**
	 * Returns a brother if it exists
	 * 
	 * @return the brother or null.
	 */
	public TreeBin getBrother() {
		if (isLastSon()) {
			return null;
		} else {
			return brother;
		}
	}

	/**
	 * Returns the depth
	 * 
	 * @return depth.
	 */
	public int getDepth() {
		return depth;
	}

	/**
	 * Returns the father
	 * 
	 * @return
	 */
	public TreeBin getFather() {
		return father;
	}

	/**
	 * Returns the level of the common father between two trees
	 * 
	 * @param tree
	 * @return level of the common father.
	 */
	public int getLevelCommonFather(TreeBin tree) {
		if (this.equals(tree)) {
			return getDepth();
		}
		int level = 0;
		TreeBin t1 = this;
		TreeBin t2 = tree;
		while (!t1.isLeaf() && !t2.isLeaf()
				&& t1.getOperand() == t2.getOperand()
				&& t1.getOperation() == t2.getOperation()) {
			level++;
			t1 = t1.getSon();
			t2 = t2.getSon();
		}
		return level;
	}

	/**
	 * Returns the max depth
	 * 
	 * @return
	 */
	public int getMaxDepth() {
		return maxDepth;
	}

	/**
	 * Returns the min depth
	 * 
	 * @return
	 */
	public int getMinDepth() {
		return minDepth;
	}

	/**
	 * Returns the num of nodes.
	 * 
	 * @return
	 */
	public int getNumNodes() {
		return numNodes;
	}

	/**
	 * Returns the number of sons
	 * 
	 * @return number of sons.
	 */
	public int getNumSons() {
		int sons = 0;
		if (!isLeaf()) {
			TreeBin t = son;
			sons++;
			t = t.getBrother();
			while (t != null) {
				t = t.getBrother();
				sons++;
			}
		}
		return sons;
	}

	/**
	 * Returns the operand
	 * 
	 * @return
	 */
	public Operand getOperand() {
		return operand;
	}

	/**
	 * Returns the operator
	 * 
	 * @return
	 */
	public Operation getOperation() {
		return operator;
	}

	/**
	 * Returns the son if it exists
	 * 
	 * @return the son or null.
	 */
	public TreeBin getSon() {
		if (isLeaf()) {
			return null;
		} else {
			return son;
		}
	}

	/**
	 * Returns all the sons of the Tree
	 * 
	 * @return the sons.
	 */
	public ArrayList<TreeBin> getSons() {
		ArrayList<TreeBin> sons = new ArrayList<TreeBin>();

		if (!isLeaf()) {
			TreeBin t = son;
			sons.add(t);
			t = t.getBrother();
			while (t != null) {
				sons.add(t);
				t = t.getBrother();
			}
		}

		return sons;
	}

	/**
	 * Returns true if the Tree is the last brother or if it is only son.
	 * 
	 * @return if there isn't any other brother.
	 */
	public boolean isLastSon() {
		return brother == null;
	}

	/**
	 * Returns true if the Tree haven't sons
	 * 
	 * @return if the actual node is a leaf.
	 */
	public boolean isLeaf() {
		return son == null;
	}

	/**
	 * Mutate a node, if it's an operand, select a random operand, else a random
	 * operator.
	 */
	public void mutate(double p) {
		Random r = new Random();

		// BFS uses queue data structure
		LinkedList<TreeBin> list = new LinkedList<TreeBin>();
		list.add(this);
		TreeBin t1 = this;
		while (!list.isEmpty()) {
			t1 = list.remove();
			list.addAll(t1.getSons());
			if (r.nextDouble() < p) {
				if (t1.isLeaf()) {
					t1.setOperand(operandRandom());
				} else {
					Operation operation = operatorRandom();
					t1.setOperation(operation);
					int numSons = t1.getNumSons();
					if (operation == Operation.IF) {
						TreeBin t2 = t1.getSon();
						if (numSons == 1) {
							t2.setBrother(new TreeBin(minDepth, maxDepth, t1));
							t2 = t2.getBrother();
							t2.setBrother(new TreeBin(minDepth, maxDepth, t1));
						} else if (numSons == 2) {
							t2 = t2.getBrother();
							t2.setBrother(new TreeBin(minDepth, maxDepth, t1));
						}
					} else if (operation == Operation.NOT) {
						if (numSons > 1) {
							t1.getSon().setBrother(null);
						}
					} else {
						if (numSons > 2) {
							t1.getSon().getBrother().setBrother(null);
						} else if (numSons < 2) {
							t1.getSon().setBrother(
									new TreeBin(minDepth, maxDepth, t1));
						}
					}
				}
			}
		}
	}

	/**
	 * Reset the pointer of fathers.
	 */
	public void resetFathers() {
		TreeBin father = this;
		// BFS uses queue data structure
		LinkedList<TreeBin> list = new LinkedList<TreeBin>();
		list.add(this);
		while (!list.isEmpty()) {
			father = list.remove();
			for (TreeBin son : father.getSons()) {
				son.setFather(father);
				list.add(son);
			}
		}
		list.clear();
	}

	/**
	 * Breadth-First Search
	 * 
	 * @param node
	 * @return
	 */
	public TreeBin searchNode(int node) {

		if (node == 0) {
			return this;
		}

		if (node < 0) {
			return null;
		}

		// BFS uses queue data structure
		LinkedList<TreeBin> list = new LinkedList<TreeBin>();
		list.add(this);
		TreeBin t = this;
		int cN = -1;
		while (cN != node && !list.isEmpty()) {
			t = list.remove();
			list.addAll(t.getSons());
			cN++;
		}
		list.clear();
		return cN == node ? t : null;

	}

	/**
	 * Set a brother.
	 * 
	 * @param brother
	 */
	public void setBrother(TreeBin brother) {
		this.brother = brother;
	}

	/**
	 * Set the depth
	 * 
	 * @param depth
	 */
	public void setDepth(int depth) {
		this.depth = depth;
	}

	public void setDepths(int minDepth, int maxDepth) {
		setMinDepth(minDepth);
		setMaxDepth(maxDepth);
	}

	/**
	 * Set the father
	 * 
	 * @param father
	 */
	public void setFather(TreeBin father) {
		this.father = father;
	}

	public void setMaxDepth(int maxDepth) {
		this.maxDepth = maxDepth;
	}

	public void setMinDepth(int minDepth) {
		this.minDepth = minDepth;
	}

	/**
	 * Set the num of nodes.
	 * 
	 * @param numNodes
	 */
	public void setNumNodes(int numNodes) {
		this.numNodes = numNodes;
	}

	/**
	 * Set operand.
	 * 
	 * @param operand
	 */
	public void setOperand(Operand operand) {
		this.operand = operand;
	}

	/**
	 * Set operation.
	 * 
	 * @param operation
	 */
	public void setOperation(Operation operation) {
		this.operator = operation;
	}

	/**
	 * Set a son.
	 * 
	 * @param son
	 */
	public void setSon(TreeBin son) {
		this.son = son;
	}

	/**
	 * Sustitute a subTree with root "node" for "tree"
	 * 
	 * @param node
	 * @param tree
	 */
	public void sustitute(int node, TreeBin tree) {
		// BFS uses queue data structure
		LinkedList<TreeBin> list = new LinkedList<TreeBin>();
		list.add(this);
		TreeBin t = this;
		int cN = -1;
		while (cN != node && !list.isEmpty()) {
			t = list.remove();
			list.addAll(t.getSons());
			cN++;
		}
		list.clear();
		TreeBin father = t.getFather();
		TreeBin brother = null;
		if (father.getSon() == t) {
			brother = father.getSon().getBrother();
			father.setSon(tree);
		} else if (father.getSon().getBrother() == t) {
			brother = father.getSon().getBrother().getBrother();
			father.getSon().setBrother(tree);
		} else {
			father.getSon().getBrother().setBrother(tree);
		}
		tree.setBrother(brother);
		tree.setFather(father);
	}

	@Override
	public String toString() {
		String s = " (";

		TreeBin t = this;
		if (t.isLeaf()) {
			s += t.getOperand();
		} else {
			s += t.getOperation();
			for (TreeBin son : t.getSons()) {
				s += son.toString();
			}
		}

		return s + ")";
	}

	public void update() {
		int[] att = update2();
		depth = att[0];
		numNodes = att[1];
	}

	private TreeBin clone(TreeBin father) {
		if (isLeaf() && isLastSon()) {
			return new TreeBin(minDepth, maxDepth, operand, operator, 0, 1,
					father);
		} else if (isLeaf()) {
			TreeBin t = new TreeBin(minDepth, maxDepth, operand, operator, 0,
					1, father);
			TreeBin brother = this.brother.clone(father);
			brother.setFather(father);
			t.setBrother(brother);
			t.setDepth(brother.getDepth());
			t.setNumNodes(brother.getNumNodes() + 1);
			return t;
		} else if (isLastSon()) {
			TreeBin t = new TreeBin(minDepth, maxDepth, operand, operator);
			TreeBin son = this.son.clone(t);
			son.setFather(t);
			t.setSon(son);
			t.setDepth(son.getDepth() + 1);
			t.setNumNodes(son.getNumNodes() + 1);
			return t;
		} else {
			TreeBin t = new TreeBin(minDepth, maxDepth, operand, operator);
			TreeBin brother = this.brother.clone(father);
			TreeBin son = this.son.clone(t);
			son.setFather(t);
			brother.setFather(father);
			t.setFather(father);
			t.setSon(son);
			t.setBrother(brother);
			t.setDepth(Math.max(son.getDepth() + 1, brother.getDepth()));
			t.setNumNodes(son.getNumNodes() + brother.getNumNodes() + 1);
			return t;
		}
	}

	/**
	 * Generate a random leaf.
	 */
	private void genLeaf() {
		setOperand(operandRandom());
		setNumNodes(1);
		setDepth(0);
	}

	/**
	 * Generate a random subTree.
	 * 
	 * @param minDepth
	 * @param maxDepth
	 */
	private void genSubTree(int minDepth, int maxDepth) {
		this.operator = operatorRandom();
		TreeBin t = this;
		// Left son
		t.setSon(new TreeBin(minDepth - 1, maxDepth - 1, this));
		t = t.getSon();
		setNumNodes(numNodes + t.getNumNodes() + 1);
		setDepth(t.getDepth() + 1);
		if (operator != Operation.NOT) {
			if (operator == Operation.IF) {
				// Center son
				t.setBrother(new TreeBin(minDepth - 1, maxDepth - 1, this));
				t = t.getBrother();
				setNumNodes(numNodes + t.getNumNodes());
				setDepth(Math.max(depth, t.getDepth() + 1));
			}
			// Right son
			t.setBrother(new TreeBin(minDepth - 1, maxDepth - 1, this));
			t = t.getBrother();
			setNumNodes(numNodes + t.getNumNodes());
			setDepth(Math.max(depth, t.getDepth() + 1));
		}
	}

	private void genSubTree2(int minDepth, int maxDepth) {
		if (maxDepth == 0) {
			genLeaf();
		} else {
			int type = new Random().nextInt(2);
			if (type == 1) {
				genSubTree(minDepth, maxDepth);
			} else {
				genLeaf();
			}
		}
	}

	private Operand operandRandom() {
		int i = new Random().nextInt(6);
		Operand operand;
		switch (i) {
		case 0:
			operand = Operand.A0;
			break;
		case 1:
			operand = Operand.A1;
			break;
		case 2:
			operand = Operand.D0;
			break;
		case 3:
			operand = Operand.D1;
			break;
		case 4:
			operand = Operand.D2;
			break;
		default:
			operand = Operand.D3;
			break;
		}
		return operand;
	}

	private Operation operatorRandom() {
		int i = new Random().nextInt(4);
		Operation operation;
		switch (i) {
		case 0:
			operation = Operation.IF;
			break;
		case 1:
			operation = Operation.AND;
			break;
		case 2:
			operation = Operation.OR;
			break;
		default:
			operation = Operation.NOT;
			break;
		}
		return operation;
	}

	private int[] update2() {
		if (isLeaf() && isLastSon()) {
			int[] sol = { 0, 1 };
			return sol;
		} else if (isLeaf()) {
			int[] sol = brother.update2();
			sol[1]++;
			return sol;
		} else if (isLastSon()) {
			int[] sol = son.update2();
			sol[0]++;
			sol[1]++;
			return sol;
		} else {
			int[] sol = son.update2();
			int[] aux = brother.update2();
			sol[0] = Math.max(sol[0] + 1, aux[0]);
			sol[1] = sol[1] + aux[1] + 1;
			return sol;
		}
	}
}